#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/22 15:17
# ===========================================
#       题目名称： 24. 两两交换链表中的节点
#       题目地址： https://leetcode.cn/problems/swap-nodes-in-pairs/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
from utils import StringUtils


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
        实现思路：
            定义一个新的链表 对新的链表进行填充
    """

    def swapPairs(self, head):
        if not head:
            return None
        if head and not head.next:
            return head
        old_node_list = head
        new_node_list = None
        while old_node_list and old_node_list.next:
            node1_val = old_node_list.val
            node2 = old_node_list.next
            node2_val = node2.val
            if new_node_list:
                temp_node = new_node_list
                while temp_node and temp_node.next:
                    temp_node = temp_node.next
                new_node1 = ListNode(node2_val)
                new_node2 = ListNode(node1_val)
                temp_node.next = new_node1
                new_node1.next = new_node2
            else:
                new_node_list = ListNode(node2_val, ListNode(node1_val))
            old_node_list = node2.next
        else:
            if old_node_list and not old_node_list.next:
                temp_node = new_node_list
                while temp_node and temp_node.next:
                    temp_node = temp_node.next
                temp_node.next = ListNode(old_node_list.val)
        return new_node_list

    def swapPairs2(self, head):
        node0 = dummy = ListNode(next=head)  # 用哨兵节点简化代码逻辑
        node1 = head
        while node1 and node1.next:  # 至少有两个节点
            node2 = node1.next
            node3 = node2.next

            node0.next = node2  # 0 -> 2
            node2.next = node1  # 2 -> 1
            node1.next = node3  # 1 -> 3

            node0 = node1  # 下一轮交换，0 是 1
            node1 = node3  # 下一轮交换，1 是 3
        return dummy.next  # 返回新链表的头节点


if __name__ == '__main__':
    s = Solution()
    # [2,1,4,3]
    print(StringUtils.to_string(s.swapPairs(ListNode(1, ListNode(2, ListNode(3, ListNode(4)))))))
    # []
    print(StringUtils.to_string(s.swapPairs(None)))
    # [1]
    print(StringUtils.to_string(s.swapPairs(ListNode(1))))
    # [2,1,3]
    print(StringUtils.to_string(s.swapPairs(ListNode(1, ListNode(2, ListNode(3))))))
